package com.easy.leetcode.array;

import java.util.HashMap;
import java.util.Map;

/**
 * @ClassName FirstMissingPositive41
 * @Description 41. 缺失的第一个正数
 * @Author zheng
 * @Date 2021/11/25 19:51
 * @Version 1.0
 **/
public class FirstMissingPositive41 {
    /**
     * 时间复杂度 O(n),空间复杂度O(n)
     **/
    public int firstMissingPositive(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, num);
        }
        int target = 0;
        while (map.get(target + 1) != null) {
            target++;
        }
        return target;
    }

    /**
     * 原地hash
     */
    public int firstMissingPositive1(int[] nums) {
        //整个数组中只放1到nums.length+1 的值，不符合的直接扔掉
        for (int i = 0; i < nums.length; i++) {
            //这里用while是因为交换回来的值不一定是"值配其位"的，那么就可能还需要进行交换
            //比如[4,1,2,3]
            //注意，此处  nums[nums[i] - 1] != nums[i]  不能用num[i-1]!= i
            while (nums[i] > 0 && nums[i] <= nums.length && nums[nums[i] - 1] != nums[i] ) {
                swap(nums, nums[i] - 1, i);
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return nums.length + 1;
    }

    public void swap(int[] nums, int index, int index1) {
        int tmp = nums[index];
        nums[index] = nums[index1];
        nums[index1] = tmp;
    }


    public static void main(String[] args) {
        FirstMissingPositive41 firstMissingPositive41 = new FirstMissingPositive41();
        firstMissingPositive41.firstMissingPositive1(new int[]{7,8,9,11,12});
    }
}
